125. 验证回文串 [简单]
题目说明
Leetcode题目链接
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
1
2
3
| 输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
|
示例 2:
1
2
3
| 输入: "race a car"
输出: false
解释："raceacar" 不是回文串
|
提示：
1 <= s.length <= 2 * 105- 字符串
s 由 ASCII 字符组成
解题思路
双指针
使用双指针 left right , 从字符串两端向中间遍历并一一比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
private:
bool is_valid(const char& c)
{
return ((c >= '0' && c <= '9')
|| (c >= 'A' && c <= 'Z')
|| (c >= 'a' && c <= 'z'));
}
bool is_equal(const char& c1, const char& c2)
{
return tolower(c1) == tolower(c2);
}
public:
bool isPalindrome(string s) {
int left = 0;
int right = s.size() - 1;
while (left < right)
{
while (!is_valid(s[left]) && left < right)
{
left++;
}
while (!is_valid(s[right]) && left < right)
{
right--;
}
if (left < right && !is_equal(s[left], s[right]))
{
return false;
}
left++;
right--;
}
return true;
}
};
|